package datastructure.find;

/**
 * @author MaoLin Wang
 * @description TODO
 * @date 2020/8/26 2:31 下午
 */
public class BinarySearchTree<T extends Comparable<? super T>> {
    private TreeNode<T> root;

    public BinarySearchTree(TreeNode<T> root) {
        this.root = root;
    }

    public int height(TreeNode<T> root) {
        if (root == null) {
            return -1;
        }
        return 1 + Math.max(height(root.lchild), height(root.rchild));
    }

    public void preOrder(TreeNode<T> root) {
        if (root != null) {
            System.out.println(root.data);
            preOrder(root.lchild);
            preOrder(root.rchild);
        }
    }

    public void midOrder(TreeNode<T> root) {
        if (root != null) {
            preOrder(root.lchild);
            System.out.println(root.data);
            preOrder(root.rchild);
        }
    }

    public void postOrder(TreeNode<T> root) {
        if (root != null) {
            preOrder(root.lchild);
            preOrder(root.rchild);
            System.out.println(root.data);
        }
    }

    public boolean contains(T data) {
        return contains(data, root);
    }

    private boolean contains(T data, TreeNode<T> root) {
        if (root == null) {
            return false;
        }
        int result = data.compareTo(root.data);
        if (result > 0) {
            return contains(data, root.rchild);
        } else if (result < 0) {
            return contains(data, root.lchild);
        } else {
            return true;
        }
    }

    public T findMin(TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        while (root.lchild != null) {
            root = root.lchild;
        }
        return root.data;
    }

    public T findMax(TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        while (root.rchild != null) {
            root = root.rchild;
        }
        return root.data;
    }

    public void insert(T data) {
        if (data == null) {
            return;
        }
        insert(data, root);
    }


    private TreeNode<T> insert(T data, TreeNode<T> root) {
        if (root == null) {
            return new TreeNode<>(data);
        }
        int result = root.data.compareTo(data);
        if (result < 0) {
            root.rchild = insert(data, root.rchild);
        } else if (result > 0) {
            root.lchild = insert(data, root.lchild);
        }
        return root;
    }

    public void delMin(){
       root= delMin(root);
    }

    private TreeNode<T> delMin(TreeNode<T> root) {
        if (root==null){
            return null;
        }
        if (root.lchild==null){
            return root.rchild;
        }
        root.lchild= delMin(root.lchild);

        return root;
    }

    public void delMax(){
        root=delMax(root);
    }

    private TreeNode<T> delMax(TreeNode<T> root) {
        if (root==null){
            return null;
        }
        if (root.rchild==null){
            return root.lchild;
        }
        root.rchild= delMax(root.rchild);
        return root;
    }

    public void remove(T data) {
        if (data == null) {
            return;
        }
        remove(data, root);
    }

    private TreeNode<T> remove(T data, TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        int result = root.data.compareTo(data);
        if (result < 0) {
            root.rchild = remove(data, root.rchild);
        } else if (result > 0) {
            root.lchild = remove(data, root.lchild);
        } else {
            if (root.lchild != null && root.rchild != null) {
                root.data = findMin(root);
                root.rchild = remove(root.data, root.rchild);
            } else {
                root = root.lchild == null ? root.rchild : root.lchild;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<>(5);
        BinarySearchTree<Integer> tree = new BinarySearchTree<>(root);
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(7);
        tree.insert(9);
        tree.insert(10);
        tree.insert(0);
        tree.remove(0);
        System.out.println(tree.contains(3));
        System.out.println(tree.findMin(root));
        tree.delMax();
        tree.delMin();
        System.out.println(tree.findMin(root));
        System.out.println(tree.findMax(root));
    }
}

class TreeNode<T> {
    T data;
    TreeNode lchild;
    TreeNode rchild;

    public TreeNode(T data) {
        this(data, null, null);
    }

    public TreeNode(T data, TreeNode lchild, TreeNode rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
        int[] a = {1};
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "data=" + data +
                ", lchild=" + lchild +
                ", rchild=" + rchild +
                '}';
    }

}